{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sparse Array Search LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #稀疏数组搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。</p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>: words = [&quot;at&quot;, &quot;&quot;, &quot;&quot;, &quot;&quot;, &quot;ball&quot;, &quot;&quot;, &quot;&quot;, &quot;car&quot;, &quot;&quot;, &quot;&quot;,&quot;dad&quot;, &quot;&quot;, &quot;&quot;], s = &quot;ta&quot;\n",
    "<strong> 输出</strong>：-1\n",
    "<strong> 说明</strong>: 不存在返回-1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>：words = [&quot;at&quot;, &quot;&quot;, &quot;&quot;, &quot;&quot;, &quot;ball&quot;, &quot;&quot;, &quot;&quot;, &quot;car&quot;, &quot;&quot;, &quot;&quot;,&quot;dad&quot;, &quot;&quot;, &quot;&quot;], s = &quot;ball&quot;\n",
    "<strong> 输出</strong>：4\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>words的长度在[1, 1000000]之间</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sparse-array-search-lcci](https://leetcode.cn/problems/sparse-array-search-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sparse-array-search-lcci](https://leetcode.cn/problems/sparse-array-search-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        left,right=0,len(words)-1\n",
    "        while left<=right:\n",
    "            mid=(right+left)//2\n",
    "            temp=mid\n",
    "            while words[mid]=='' and mid<right:\n",
    "                mid+=1\n",
    "            if words[mid]=='':\n",
    "                right=temp-1\n",
    "                continue\n",
    "            if words[mid]==s:\n",
    "                return mid\n",
    "            elif s<words[mid]:\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        # 使用双向查找\n",
    "        i=0\n",
    "        j=len(words)-1\n",
    "        while i<j and words[i]!=s:\n",
    "            i+=1\n",
    "        while i<j and words[j]!=s:\n",
    "            j-=1\n",
    "        if words[i]==s:\n",
    "            return i\n",
    "        elif words[j]==s:\n",
    "            return j\n",
    "        else:\n",
    "            return -1\n",
    "        \n",
    "            \n",
    "        \n",
    "        # 使用自带函数求解\n",
    "        if s in words:\n",
    "            return words.index(s)\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        return words.index(s) if s in words else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        # if s in words:\n",
    "        #     return words.index(s)\n",
    "        # else:\n",
    "        #     return -1\n",
    "        return words.index(s) if s in words else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for enu, i in enumerate(words):\n",
    "            if i == s:\n",
    "                return enu\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        # return words.index(s) if s in words else -1\n",
    "\n",
    "        lw = len(words)\n",
    "        l, r = 0, lw-1\n",
    "        while l <= r:\n",
    "            m = l + (r-l)//2\n",
    "            t = m\n",
    "            while m < r and words[m] == \"\":\n",
    "                m += 1\n",
    "            if words[m] == '':\n",
    "                r = t-1\n",
    "                continue\n",
    "                \n",
    "            if words[m] == s:\n",
    "                return m\n",
    "            elif words[m] < s:\n",
    "                l = m+1\n",
    "            elif words[m] > s:\n",
    "                r = m-1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        def find(start, end):\n",
    "            if start > end:\n",
    "                return -1\n",
    "            \n",
    "            while start <= end:\n",
    "                mid = (start + end) // 2\n",
    "                if words[mid] == s:\n",
    "                    return mid\n",
    "                elif words[mid] == '':\n",
    "                    tmp = mid - 1\n",
    "                    while mid < end and words[mid] == '':\n",
    "                        mid += 1\n",
    "                    if words[mid] > s:\n",
    "                        end = tmp\n",
    "                    elif words[mid] == s:\n",
    "                        return mid\n",
    "                    else:\n",
    "                        start = mid + 1\n",
    "                elif words[mid] > s:\n",
    "                    end = mid - 1\n",
    "                else:\n",
    "                    start = mid + 1\n",
    "            return -1\n",
    "        return find(0, words.__len__()-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        try:\n",
    "            return words.index(s)\n",
    "        except:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        left, right = 0, len(words)-1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            temp = mid\n",
    "            while words[mid] == \"\" and mid < right:\n",
    "                mid += 1\n",
    "            if words[mid] == \"\":\n",
    "                right = temp - 1\n",
    "                continue\n",
    "            if words[mid] > s:\n",
    "                right = temp - 1\n",
    "            elif words[mid] < s:\n",
    "                left = temp + 1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        dic = dict()\n",
    "        for i,w in enumerate(words):\n",
    "            dic[w] = i\n",
    "        \n",
    "        if s in dic:\n",
    "            return dic[s]\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == \"\":\n",
    "                continue\n",
    "            elif words[i] == s:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        n = len(words)\n",
    "        l,r = 0,n-1\n",
    "        while l<=r:\n",
    "            while l<n and words[l]=='':\n",
    "                l+=1\n",
    "            if l<n and words[l]==s:return l\n",
    "            while r>=0 and words[r]=='':\n",
    "                r-=1\n",
    "            if r>=0 and words[r]==s:return r\n",
    "            mid = (l+r)//2\n",
    "            while words[mid]=='' and mid>=l:\n",
    "                mid-=1\n",
    "            if words[mid]<s:\n",
    "                l = mid+1\n",
    "            elif words[mid]>s:\n",
    "                r = mid-1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for i in range(len(words)):\n",
    "             if words[i] == s:\n",
    "                 return i\n",
    "        return -1\n",
    "             \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findString(self, words: List[str], s: str) -> int:\n",
    "\t\tfor i in range(len(words)):\n",
    "\t\t\tif words[i] == s:\n",
    "\t\t\t\treturn i\n",
    "\t\treturn -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == s: return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        try:\n",
    "            return words.index(s)\n",
    "        except:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        word2ind = {word: ind for ind, word in enumerate(words)}\n",
    "        return word2ind.get(s, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findString(self, words: List[str], s: str) -> int:\n",
    "\t\tdic = {}\n",
    "\t\tfor i in range(len(words)):\n",
    "\t\t\tdic[words[i]] = i\n",
    "\t\treturn dic[s] if s in dic else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findString(self, words: List[str], s: str) -> int:\n",
    "\t\treturn words.index(s) if s in words else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        i, j = 0, len(words) - 1\n",
    "        while i <= j:\n",
    "            \n",
    "            idx = (i + j)// 2\n",
    "            while words[idx] == '' and idx > i:\n",
    "                idx -= 1\n",
    "            if words[idx] == s:\n",
    "                print('2222222222222222')\n",
    "                return idx\n",
    "            if words[idx] > s:\n",
    "                j = idx - 1\n",
    "            if words[idx] < s:\n",
    "                i = idx + 1\n",
    "            print(i, j)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        left, right = 0, len(words) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            temp = mid  # 记录一下mid的位置，因为下面要移动mid来寻找非空串，如果查找失败需要用temp来恢复位置\n",
    "            while words[mid] == '' and mid < right:  # 如果mid对应空串则向右寻找\n",
    "                mid += 1\n",
    "            if words[mid] == '':  \n",
    "            # 该情况发生在mid走到了right-1的位置，如果right仍对应空，则说明temp右侧都是空，所以将右边界进行改变\n",
    "                right = temp - 1\n",
    "                continue\n",
    "            if words[mid] == s:  # 该情况发生在mid在右移的过程中发现了非空串，则进行正常的二分查找\n",
    "                return mid\n",
    "            elif s < words[mid]:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for i in range(len(words)):\n",
    "            if words[i]!='':\n",
    "                if s==words[i]:\n",
    "                    return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for index,st in enumerate(words):\n",
    "            if st==s:\n",
    "                return index\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == s:\n",
    "                return i\n",
    "        else:\n",
    "            return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        left, right = 0, len(words) - 1\n",
    "        n = len(words)\n",
    "        while left <= right:\n",
    "            while left <= right and not words[left]:\n",
    "                left += 1\n",
    "            while left <= right and not words[right]:\n",
    "                right -= 1\n",
    "            if left > right:\n",
    "                return -1\n",
    "            mid = (left + right) // 2\n",
    "            while mid >= left and not words[mid]:\n",
    "                mid -= 1\n",
    "            if words[mid] == s:\n",
    "                return mid\n",
    "            elif words[mid] > s:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        index = 0\n",
    "        for word in words:\n",
    "            if word == s:\n",
    "                return index\n",
    "            index += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        try:\n",
    "            return words.index(s)\n",
    "        except:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == s:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        if s not in words:\n",
    "            return -1\n",
    "        else:\n",
    "            return words.index(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        left, right = 0, len(words) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            temp = mid  # 记录一下mid的位置，因为下面要移动mid来寻找非空串，如果查找失败需要用temp来恢复位置\n",
    "            while words[mid] == '' and mid < right:  # 如果mid对应空串则向右寻找\n",
    "                mid += 1\n",
    "            if words[mid] == '':  \n",
    "            # 该情况发生在mid走到了right-1的位置，如果right仍对应空，则说明temp右侧都是空，所以将右边界进行改变\n",
    "                right = temp - 1\n",
    "                continue\n",
    "            if words[mid] == s:  # 该情况发生在mid在右移的过程中发现了非空串，则进行正常的二分查找\n",
    "                return mid\n",
    "            elif s < words[mid]:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        n = len(words)\n",
    "        l,r = 0,n-1\n",
    "        while l<=r:\n",
    "            while l<n and words[l]=='':\n",
    "                l+=1\n",
    "            while r>=0 and words[r]=='':\n",
    "                r-=1\n",
    "            mid = (l+r)//2\n",
    "            while words[mid]=='' and mid>=l:\n",
    "                mid-=1\n",
    "            if words[mid]<s:\n",
    "                l = mid+1\n",
    "            elif words[mid]>s:\n",
    "                r = mid-1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        # for i,word in enumerate(words):\n",
    "        #     if not len(word):\n",
    "        #         continue\n",
    "        #     if word == s:\n",
    "        #         return i\n",
    "        # return -1\n",
    "        # 二分查找\n",
    "        left = 0 \n",
    "        right = len(words) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            temp = mid\n",
    "            while words[mid] == \"\" and mid > left:\n",
    "                mid -= 1\n",
    "            if words[mid] == \"\":\n",
    "                left = temp + 1\n",
    "                continue\n",
    "            if words[mid] == s:\n",
    "                return mid\n",
    "            elif s < words[mid]:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def find(words, l, r, s):\n",
    "    if r<l:\n",
    "        return -1\n",
    "    mid=(l+r)//2\n",
    "    if words[mid]==s:\n",
    "        return mid\n",
    "    if words[mid]=='':\n",
    "        r1,r2=find(words,l,mid-1,s),find(words,mid+1,r,s)\n",
    "        if r1!=-1:\n",
    "            return r1\n",
    "        if r2!=-1:\n",
    "            return r2\n",
    "        return -1\n",
    "    else:\n",
    "        if s>words[mid]:\n",
    "            return find(words, mid+1, r,s)\n",
    "        else:\n",
    "            return find(words, l, mid-1, s)\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        return find(words, 0, len(words)-1, s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        l, r = 0, len(words) - 1\n",
    "        while l <= r:\n",
    "            m = (l + r) >> 1\n",
    "            temp = m\n",
    "            while m < r and words[m] == '':\n",
    "                m += 1\n",
    "            if words[m] == '':\n",
    "                r = temp - 1\n",
    "                continue\n",
    "            if words[m] == s:\n",
    "                return m\n",
    "            elif words[m] < s:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        if s in words:\n",
    "            return words.index(s)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        n = len(words)\n",
    "        l,r = 0,n-1\n",
    "        while l<=r:\n",
    "            while l<n and words[l]=='':\n",
    "                l+=1\n",
    "            if l<n and words[l]==s:return l\n",
    "            while r>=0 and words[r]=='':\n",
    "                r-=1\n",
    "            if r>=0 and words[r]==s:return r\n",
    "            mid = (l+r)//2\n",
    "            while words[mid]=='' and mid>=l:\n",
    "                mid-=1\n",
    "            if words[mid]<s:\n",
    "                l = mid+1\n",
    "            elif words[mid]>s:\n",
    "                r = mid-1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for i, w in enumerate(words):\n",
    "            if len(w) == 0:\n",
    "                continue\n",
    "            if w == s:\n",
    "                return i\n",
    "            elif w[0] > s[0]:\n",
    "                break\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        l, r = 0, len(words) - 1\n",
    "        while l <= r:\n",
    "            m = (l + r) >> 1\n",
    "            temp = m\n",
    "            while m < r and words[m] == '':\n",
    "                m += 1\n",
    "            if words[m] == '':\n",
    "                r = temp - 1\n",
    "                continue\n",
    "            if words[m] == s:\n",
    "                return m\n",
    "            elif words[m] < s:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = temp - 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for  i in range(len(words)):\n",
    "            if words[i]==s:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        # 稀疏数组排序，数组是已经排好序的字符数组，其中散布一些空的字符串\n",
    "        for i in range(len(words)- 1,   -1,   -1):\n",
    "            if words[i]:\n",
    "                right = i + 1\n",
    "                break\n",
    "        left = 0\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if words[mid] == s:\n",
    "                return mid\n",
    "            elif not words[mid]:\n",
    "                temp = mid\n",
    "                while mid < len(words):\n",
    "                    mid += 1\n",
    "                    if mid < len(words) and words[mid] == s:\n",
    "                        return mid\n",
    "                right = temp\n",
    "            elif words[mid] < s:\n",
    "                left = mid + 1\n",
    "            elif words[mid] > s:\n",
    "                right = mid\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        if s not in words:\n",
    "            return -1\n",
    "        else:\n",
    "            return words.index(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        left = 0\n",
    "        right = len(words) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            temp = mid\n",
    "            while words[mid] == \"\" and mid < right:\n",
    "                mid += 1\n",
    "            if words[mid] == \"\":\n",
    "                right = temp - 1\n",
    "                continue\n",
    "            if words[mid] == s:\n",
    "                return mid\n",
    "            elif s < words[mid]:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        l, r = 0, len(words) - 1\n",
    "        while l < r and len(words[l]) == 0:\n",
    "            l += 1\n",
    "        while r > l and len(words[r]) == 0:\n",
    "            r -= 1\n",
    "        if len(words[l]) == 0:\n",
    "            return -1\n",
    "        while r - l > 1:\n",
    "            mid = (l + r) // 2\n",
    "            t = mid\n",
    "            while t < r and len(words[t]) == 0:\n",
    "                t += 1\n",
    "            if s == words[t]:\n",
    "                return t\n",
    "            if t < r:\n",
    "                if s < words[t]:\n",
    "                    r = t\n",
    "                else:\n",
    "                    l = t\n",
    "            else:\n",
    "                t = mid\n",
    "                while t > l and len(words[t]) == 0:\n",
    "                    t -= 1\n",
    "                if s == words[t]:\n",
    "                    return t\n",
    "                if t > l:\n",
    "                    if s > words[t]:\n",
    "                        l = t\n",
    "                    else:\n",
    "                        r = t\n",
    "                else:\n",
    "                    break\n",
    "        if words[l] == s:\n",
    "            return l\n",
    "        if words[r] == s:\n",
    "            return r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        l, r = 0, len(words) - 1\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (r - l)//2 + l\n",
    "            if words[mid] == s:\n",
    "                return mid \n",
    "            if words[mid] == \"\":\n",
    "                temp = mid - 1\n",
    "                while temp >0 and words[temp] == \"\":\n",
    "                    temp -= 1\n",
    "                \n",
    "                if words[temp] == s:\n",
    "                    return temp \n",
    "                if words[temp] > s:\n",
    "                    r = temp - 1\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            elif words[mid] > s:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        l, r = 0, len(words) - 1\n",
    "        while l < len(words) and words[l] == \"\":\n",
    "            l += 1\n",
    "        while r >= 0 and words[r] == \"\":\n",
    "            r -= 1\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            while mid <= r and words[mid] == \"\":\n",
    "                mid += 1\n",
    "            if mid > r:\n",
    "                r = l + (r - l) // 2 - 1\n",
    "                continue\n",
    "            if words[mid] == s:\n",
    "                return mid\n",
    "            elif words[mid] < s:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        left, right = 0, len(words)-1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            temp = mid\n",
    "            while mid < len(words) and words[mid] == \"\":\n",
    "                mid += 1\n",
    "            if mid == len(words):\n",
    "                right = temp - 1\n",
    "                continue\n",
    "            if words[mid] == s:\n",
    "                return mid\n",
    "            elif words[mid] > s:\n",
    "                right = temp - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        n = len(words)\n",
    "        l,r = 0,n-1\n",
    "        while l<=r:\n",
    "            while l<n and words[l]=='':\n",
    "                l+=1\n",
    "            if l<n and words[l]==s:return l\n",
    "            while r>=0 and words[r]=='':\n",
    "                r-=1\n",
    "            if r>=0 and words[r]==s:return r\n",
    "            mid = (l+r)//2\n",
    "            while words[mid]=='' and mid>=l:\n",
    "                mid-=1\n",
    "            if words[mid]<s:\n",
    "                l = mid+1\n",
    "            elif words[mid]>s:\n",
    "                r = mid-1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        dic = {}\n",
    "        for i, w in enumerate(words):\n",
    "            # if w in dic:\n",
    "                # continue\n",
    "            dic[w] = i\n",
    "        if s in dic:\n",
    "            return dic[s]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        left, right = 0, len(words)-1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            temp = mid\n",
    "            while words[mid] == \"\" and mid < right:\n",
    "                mid += 1\n",
    "            if words[mid] == \"\":\n",
    "                right = temp - 1\n",
    "                continue\n",
    "            if words[mid] > s:\n",
    "                right = mid - 1\n",
    "            elif words[mid] < s:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        n = len(words)\n",
    "        l,r = 0,n-1\n",
    "        while l<=r:\n",
    "            while l<n and words[l]=='':\n",
    "                l+=1\n",
    "            if l<n and words[l]==s:return l\n",
    "            while r>=0 and words[r]=='':\n",
    "                r-=1\n",
    "            if r>=0 and words[r]==s:return r\n",
    "            mid = (l+r)//2\n",
    "            while words[mid]=='' and mid>=0:\n",
    "                mid-=1\n",
    "            if words[mid]<s:\n",
    "                l = mid+1\n",
    "            elif words[mid]>s:\n",
    "                r = mid-1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findString(self, words: List[str], s: str) -> int:\t\n",
    "\t\tlow, high = 0, len(words)-1\n",
    "\t\twhile low <= high:\n",
    "\t\t\t# words[high] 不能为空，否则 words[mid] 可能为空，进入死循环\n",
    "\t\t\twhile high > 0 and words[high] == \"\" :\n",
    "\t\t\t\thigh=high-1\n",
    "\t\t\tmid = low + (high-low)//2\n",
    "\t\t\twhile mid < high and words[mid] == \"\":\n",
    "\t\t\t\tmid=mid+1\n",
    "\t\t\t# println(low, high, mid)\n",
    "\t\t\tif words[mid] < s:\n",
    "\t\t\t\tlow = mid + 1\n",
    "\t\t\telif words[mid] > s:\n",
    "\t\t\t\thigh = mid - 1\n",
    "\t\t\telse:\n",
    "\t\t\t\treturn mid\n",
    "\t\treturn -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == s:\n",
    "                return i \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == s:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        left = 0\n",
    "        right = len(words ) - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right)// 2\n",
    "            while words[mid] == '' and mid > left:\n",
    "                mid -= 1\n",
    "            if words[mid] > s: right = mid - 1\n",
    "            if words[mid] < s: left = mid + 1\n",
    "            if words[mid] == s: return mid\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        #   输入：words = [\"at\", \"\", \"\", \"\", \"ball\", \"\", \"\", \"car\", \"\", \"\",\"dad\", \"\", \"\"],\n",
    "        # s = \"ball\"\n",
    "        #  输出：4\n",
    "        l, r = 0, len(words) - 1\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if words[m] == \"\":\n",
    "                if words[l] != s:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    return l\n",
    "            elif words[m] < s:\n",
    "                l = m + 1\n",
    "            elif words[m] > s:\n",
    "                r = m - 1\n",
    "            else:\n",
    "                return m\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[\"at\", \"\", \"\", \"\", \"ball\", \"\", \"\", \"car\", \"\", \"\",\"dad\", \"\", \"\"]\n",
    "\"ta\"\n",
    "[\"at\", \"\", \"\", \"\", \"ball\", \"\", \"\", \"car\", \"\", \"\",\"dad\", \"\", \"\"]\n",
    "\"ball\"\n",
    "\n",
    "1 <= words.length <= 1^6\n",
    "\n",
    "Array, String, Binary Search\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        l, r = 0, len(words)-1\n",
    "        while l <= r:\n",
    "            while not words[l]: l += 1\n",
    "            while not words[r]: r -= 1\n",
    "            m = l + ((r-l)>>1)\n",
    "            while m > 0 and not words[m]: m -= 1\n",
    "            if words[m] == s: return m\n",
    "            elif words[m] > s: r = m-1\n",
    "            else: l = m+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        if s not in words:\n",
    "            return -1\n",
    "        return words.index(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        index = []\n",
    "        for i, j in enumerate(words):\n",
    "            if j:\n",
    "                index.append(i)\n",
    "        left = 0\n",
    "        right = len(index) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            print(left, right)\n",
    "            if s > words[index[mid]]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return index[left] if words[index[left]] == s else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for i,j in enumerate(words):\n",
    "            if j == s:return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        n = len(words)\n",
    "        l,r = 0,n-1\n",
    "        while l<=r:\n",
    "            while l<n and words[l]=='':\n",
    "                l+=1\n",
    "            while r>=0 and words[r]=='':\n",
    "                r-=1\n",
    "            mid = (l+r)//2\n",
    "            while words[mid]=='' and mid>=l:\n",
    "                mid-=1\n",
    "            if words[mid]<s:\n",
    "                l = mid+1\n",
    "            elif words[mid]>s:\n",
    "                r = mid-1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        l,r=0,len(words)-1\n",
    "        while(l<=r):\n",
    "            mid=(l+r)//2\n",
    "            while(words[mid]==\"\"):\n",
    "                mid-=1\n",
    "            if(words[mid]<s):\n",
    "                l+=1\n",
    "            elif(words[mid]>s):\n",
    "                r-=1\n",
    "            else:\n",
    "                if (words[mid]==s):\n",
    "                    return mid\n",
    "                    break\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        ww = [(w, i) for i, w in enumerate(words) if w != '']\n",
    "        left, right = -1, len(ww)\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if ww[mid][0] == s:\n",
    "                return ww[mid][1]\n",
    "            elif ww[mid][0] < s:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findString(self, words : List[str], s : str) -> int:\n",
    "        l, r = 0, len(words) - 1\n",
    "        for _ in range(100):\n",
    "            mid = (l + r) // 2\n",
    "            t = mid\n",
    "            while t < r and words[t] == '':\n",
    "                t += 1\n",
    "            if words[t] == s:\n",
    "                return t\n",
    "            elif words[t] == '':\n",
    "                r = mid - 1\n",
    "            elif words[t] < s:\n",
    "                l = t + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findString(self, words: List[str], s: str) -> int:\n",
    "#         l,r=0,len(words)-1\n",
    "#         while l<=r:\n",
    "#             while l<=r and not words[l]:\n",
    "#                 l+=1\n",
    "#             while l<=r and not words[r]:\n",
    "#                 r-=1\n",
    "#             if l>r:return -1\n",
    "#             mid=(l+r)//2\n",
    "#             ### 当中点为空字符串时的处理（key）\n",
    "#             while mid>=l and not words[mid]:\n",
    "#                 mid-=1\n",
    "#             if words[mid]==s:\n",
    "#                 return mid \n",
    "#             elif words[mid]>s:\n",
    "#                 r=mid-1\n",
    "#             else:\n",
    "#                 l=mid+1\n",
    "#         return -1\n",
    "\n",
    "# 作者：木子\n",
    "# 链接：https://leetcode.cn/problems/sparse-array-search-lcci/\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        left, right = 0, len(words) - 1\n",
    "        n = len(words)\n",
    "        while left <= right:\n",
    "            while left <= right and not words[left]:\n",
    "                left += 1\n",
    "            while left <= right and not words[right]:\n",
    "                right -= 1\n",
    "            if left > right:\n",
    "                return -1\n",
    "            mid = (left + right) // 2\n",
    "            while mid >= left and not words[mid]:\n",
    "                mid -= 1\n",
    "            if words[mid] == s:\n",
    "                return mid\n",
    "            elif words[mid] > s:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return -1\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[\"\", \"\", \"\"]\n",
    "\"ta\"\n",
    "[\"at\", \"\", \"\", \"\", \"ball\", \"\", \"\", \"car\", \"\", \"\",\"dad\", \"\", \"\"]\n",
    "\"ta\"\n",
    "[\"at\", \"\", \"\", \"\", \"ball\", \"\", \"\", \"car\", \"\", \"\",\"dad\", \"\", \"\"]\n",
    "\"ball\"\n",
    "\n",
    "1 <= words.length <= 1^6\n",
    "\n",
    "Array, String, Binary Search\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        n = len(words)\n",
    "        l, r = 0, n-1\n",
    "        while l <= r:\n",
    "            while l < n and not words[l]: l += 1\n",
    "            while r >= 0 and not words[r]: r -= 1\n",
    "            if l > r: break\n",
    "            m = l + ((r-l)>>1)\n",
    "            while m > 0 and not words[m]: m -= 1\n",
    "            if words[m] == s: return m\n",
    "            elif words[m] > s: r = m-1\n",
    "            else: l = m+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        if s in words:\n",
    "            return words.index(s)\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        left = 0\n",
    "        right = len(words) - 1 \n",
    "\n",
    "        while left <= right:\n",
    "            while left < right and words[left] == '':\n",
    "                left += 1\n",
    "            \n",
    "            while left < right and words[right] == '':\n",
    "                right -= 1 \n",
    "            \n",
    "            mid = left + (right-left) // 2\n",
    "\n",
    "            while mid > left and words[mid] == '':\n",
    "                mid -= 1 \n",
    "            \n",
    "            if words[mid] == s:\n",
    "                return mid \n",
    "            \n",
    "            if words[mid] < s:\n",
    "                left = mid + 1\n",
    "            elif words[mid] > s:\n",
    "                right = mid - 1\n",
    "            \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        # for i,word in enumerate(words):\n",
    "        #     if not len(word):\n",
    "        #         continue\n",
    "        #     if word == s:\n",
    "        #         return i\n",
    "        # return -1\n",
    "        # 二分查找\n",
    "        left = 0 \n",
    "        right = len(words) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            temp = mid\n",
    "            while words[mid] == \"\" and mid < right:\n",
    "                mid += 1\n",
    "            if words[mid] == \"\":\n",
    "                right = temp - 1\n",
    "                continue\n",
    "            if words[mid] == s:\n",
    "                return mid\n",
    "            elif s < words[mid]:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        return words.index(s) if s in words else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        left, right = 0, len(words)-1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            temp = mid\n",
    "            while words[mid] == \"\" and mid < right:\n",
    "                mid += 1\n",
    "            if words[mid] == \"\":\n",
    "                right = temp - 1\n",
    "                continue\n",
    "            if words[mid] > s:\n",
    "                right = temp - 1\n",
    "            elif words[mid] < s:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                return mid\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == s:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        i, j = 0, len(words) - 1\n",
    "        while i <= j:\n",
    "            \n",
    "            idx = int((i+j)/2)\n",
    "            while words[idx] == '' and idx > i and idx - 1 >=0:\n",
    "                idx -= 1\n",
    "            \n",
    "            if words[idx] == s:\n",
    "                return idx\n",
    "            if words[idx] < s:\n",
    "                i = idx + 1\n",
    "            if words[idx] > s:\n",
    "                j = idx - 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        l,r=0,len(words)-1\n",
    "        while l<=r:\n",
    "            while l<=r and not words[l]:\n",
    "                l+=1\n",
    "            while l<=r and not words[r]:\n",
    "                r-=1\n",
    "            if l>r:return -1\n",
    "            mid=(l+r)//2\n",
    "            while mid>=l and not words[mid]:\n",
    "                mid-=1\n",
    "            if words[mid]==s:\n",
    "                return mid \n",
    "            elif words[mid]>s:\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findString(self, words: List[str], s: str) -> int:\n",
    "        if s in words:\n",
    "            return words.index(s)\n",
    "        else:\n",
    "            return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
